package leetcode.offer_two_special.linked;

/**
 * @author mazouri
 * @create 2021-09-07 23:16
 */
public class _29_insert {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            Node newHead = new Node(insertVal);
            newHead.next = newHead;
            return newHead;
        }
        Node max = null;
        Node cur = head;
        do {
            if (insertVal >= cur.val && insertVal <= cur.next.val) {
                cur.next = new Node(insertVal, cur.next);
                return head;
            }
            if (cur.val > cur.next.val) {
                max = cur;
            }
            cur = cur.next;
        } while (cur != head);
        max = max == null ? cur : max;
        max.next = new Node(insertVal, max.next);
        return head;
    }
    static class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }
}


